Computations and Comparisons on Privately Held Data
Secure comparison of two data instances, such as images, videos, sounds, texts, without revealing the data instances is part of secure multiparty computation. If a function of two data instances can be expressed as an algebraic circuit, then there usually exists a generalized protocol to compute the function while satisfying various privacy requirements. In practice, however, such a generalized protocol is extremely complex in terms of computation and communication overhead. Therefore, it is necessary to develop efficient protocols for commonly used functions, such as a Euclidean distance, a Hamming distance, or a cross-correlation.
Homomorphic Cryptosystems
A number of methods use public-key homomorphic cryptosystems for computing functions in an encrypted domain. The homomorphic cryptosystems can be classified as additively, multiplicatively, or doubly homomorphic cryptosystems. Such cryptosystems have been used to construct privacy preserving protocols for comparing strings, clustering nearest-neighbors, recognizing faces, authenticating biometric data, and other applications.
Most of those methods require encryption of the data using a public encryption key of a client performing a query, and operate in two stages: (1) secure computation of the distance or correlation between data instances; and (2) information retrieval based on a distance criterion. While those methods can be efficient for a single query, the methods may not scale for multiple clients simultaneously querying a database stored at a server. For example, if several clients retrieve similar images from the server, the entire protocol is replicated using the encryption/decryption key pair of each client. For several concurrent queries, a large amount of ciphertext is produced, which is discarded later.
Accordingly, it is desired to encrypt the data on the server only once, such that the data can be retrieved by various clients in a privacy preserving manner.
Attribute-Based Encryption (ABE)
In a conventional cryptosystem, when the server needs to transmit a data instance securely to the client, the server must encrypt the data instance either with a symmetric key known to server and the client, or with a public key of the client. Instead, in the ABE system, the server obtains some public encryption parameters from a key authority (KA) and generates a ciphertext that includes two components: the encryption of the data instance and a data instance attribute extracted from the data instance.
In order to perform decryption, the client uses its attribute to request a decryption key from the KA. For example, the client can decrypt the data instance if and only if a dot product of the attributes of the client and the server is zero, see Katz et al., Predicate Encryption Supporting Disjunction, Polynomial Equations, & Inner Products,” in EUROCRYPT, Istanbul, Turkey, pp. 146-162, April 2008.
However, the above method has a number of practical limitations. First, the construction based on the dot product cannot directly be used to compare two data instances, with respect to a distance metric such as the Hamming distance, the Euclidean distance, etc. Second, the construction requires the KA, which can be disadvantageous in a number of applications, because the KA issues client-specific or server-specific decryption keys and thus has full knowledge of both keys. A trusted (non-malicious) KA with such significant powers can be difficult to replicate in practice.
Bilinear Groups of Composite Order
An example of bilinear groups of composite order, is when the group order N is a product of three primes. Let N=pqr, where p, q, r are three different prime numbers. Let G and GT be cyclic groups of order N. Then, a mapping e:G×G→GT is a non-degenerate bilinear map if the mapping satisfies e(xα, yβ)=e(x,y)αβ where x, y are elements of G and α, β are integers. Further, if g is a generator of G, then e(g, g) is a generator of GT.
Consider the cyclic groups Gp, Gq and Gr with orders p, q and r respectively and generators gp, gq and gr respectively. Then G=Gp×Gq×Gr and any element x in the set G can be represented as x=gpαgqβgrγ, where α, β, γ are integers.
The bilinear map e(·,·) has the following properties:e(gpα,gqβ)=1e(gpα,gqβ,gqβ)=e(gqδ,gqβ),e(gpα,gpβgpδ)=e(gpα,gpβ)·e(gpα,gpδ), ande(gpαgqβ,gpγgqδ)=e(gpα,gpγ)·e(gpβ,gqδ).
Proving these properties involves an application of the definition of the bilinear mapping given above, and the properties of multiplicative cyclic groups.
Mathematically Intractable Problems
The security of the attribute-based cryptosystems using bilinear groups of composite order reduces to solving two problems, described below, that are regarded as computationally intractable. Consider an integer N=pqr for large primes p, q, r and a cyclic group G=Gp×Gq×Gr.
Then, the following problems are thought to be mathematically intractable:                1. Subgroup Decision Problem: It is computationally hard to distinguish elements of the subgroup Gp×Gq from an element of the group G. In other words, it is computationally hard to determine whether an element is drawn from a uniform distribution on G, or from a uniform distribution on the subgroup Gp×Gq.        2. Pairing Diffie-Hellman Problem: Consider a bilinear map e:G×G→GT. Choose g as one element from the set        
                    L                            SEP              ⁢            {                        g          p                ,                  g          q                ,                  g          r                    }        .  Suppose that e( g, g)v is given and an integer
                    L                            SEP              ⁢  uis chosen at random. Then, it is computationally hard to distinguish e( g, g)uv, an element of GT from a randomly chosen element of GT. Another way of stating this is that, given e( g, g)v, it is computationally hard to obtain v.
Both these assumptions are related to the computational intractability of finding non-trivial prime factors of a large number N. A detailed discussion of proving the security of an ABE system based on bilinear groups of composite order, see Katz et al.